home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Entertainment / MacMud / Mud 4.0 / smalloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-09-30  |  11.9 KB  |  543 lines  |  [TEXT/tefi]
  1. /* Satoria's malloc intended to be optimized for lpmud.
  2. ** this memory manager distinguishes between two sizes
  3. ** of blocks: small and large.  It manages them separately
  4. ** in the hopes of avoiding fragmentation between them.
  5. ** It expects small blocks to mostly be temporaries.
  6. ** It expects an equal number of future requests as small
  7. ** block deallocations.
  8. */
  9. #include <stdio.h>
  10. #include <memory.h>
  11. #include "lint.h"
  12. #include "config.h"
  13. #ifdef NLHACK
  14. extern void log_sbrk PROT((unsigned));
  15. #endif
  16. #ifdef MSDOS
  17. #define char void
  18. #endif
  19.  
  20. #define fake(s)
  21. #define smalloc malloc
  22. #define sfree free
  23. #define srealloc realloc
  24.  
  25. #define SMALL_BLOCK_MAX_BYTES    32
  26. #define SMALL_CHUNK_SIZE    0x4000
  27. #define CHUNK_SIZE        0x40000
  28.  
  29. #define SINT sizeof(int)
  30. #define SMALL_BLOCK_MAX (SMALL_BLOCK_MAX_BYTES/SINT)
  31.  
  32. #define PREV_BLOCK    0x80000000
  33. #define THIS_BLOCK    0x40000000
  34. #define MASK        0x0FFFFFFF
  35.  
  36. #define MAGIC        0x17952932
  37.  
  38. /* SMALL BLOCK info */
  39.  
  40. typedef unsigned int u;
  41.  
  42. static u *sfltable[SMALL_BLOCK_MAX];    /* freed list */
  43. static u *next_unused;
  44. static u unused_size;            /* until we need a new chunk */
  45.  
  46. /* LARGE BLOCK info */
  47.  
  48. static u *free_list;
  49. static u *start_next_block;
  50.  
  51. /* STATISTICS */
  52.  
  53. static int small_count[SMALL_BLOCK_MAX];
  54. static int small_total[SMALL_BLOCK_MAX];
  55. static int small_max[SMALL_BLOCK_MAX];
  56. static int small_free[SMALL_BLOCK_MAX];
  57.  
  58. typedef struct { unsigned counter, size; } stat;
  59. #define count(a,b) { a.size+=(b); if ((b)<0) --a.counter; else ++a.counter; }
  60.  
  61. int debugmalloc;    /* Only used when debuging malloc() */
  62.  
  63. /********************************************************/
  64. /*  SMALL BLOCK HANDLER                    */
  65. /********************************************************/
  66.  
  67. static char *large_malloc();
  68. static void large_free();
  69.  
  70. #define s_size_ptr(p)    (p)
  71. #define s_next_ptr(p)    ((u **) (p+1))
  72.  
  73. stat small_alloc_stat;
  74. stat small_free_stat;
  75. stat small_chunk_stat;
  76.  
  77. char *smalloc(size)
  78.   u size;
  79. {
  80.   int i;
  81.   u *temp;
  82.  
  83.   if (size == 0)
  84.       fatal("Malloc size 0.\n");
  85.   if (size>SMALL_BLOCK_MAX_BYTES)
  86.     return large_malloc(size,0);
  87.  
  88.   i = (size - 1) >> 2;
  89.   size = i+2;                /* block size in ints */
  90.   count(small_alloc_stat,size << 2);
  91.  
  92.   small_count[i] += 1;            /* update statistics */
  93.   small_total[i] += 1;
  94.   if (small_count[i] >= small_max[i])
  95.     small_max[i] = small_count[i];
  96.  
  97.   if (sfltable[i]) 
  98.     {                    /* allocate from the free list */
  99.       count(small_free_stat, -(int) (size << 2));
  100.       temp = sfltable[i];
  101.       sfltable[i] = * (u **) (temp+1);
  102. fake("From free list.");
  103.       return (char *) (temp+1);
  104.     }                    /* else allocate from the chunk */
  105.  
  106.   if (unused_size<size)            /* no room in chunk, get another */
  107.     {
  108.       fake("Allocating new small chunk.");
  109.       next_unused = (u *) large_malloc(SMALL_CHUNK_SIZE,1);
  110.       if (next_unused == 0)
  111.     return 0;
  112.       count(small_chunk_stat, SMALL_CHUNK_SIZE+SINT);
  113.       unused_size = SMALL_CHUNK_SIZE / SINT;
  114.     }
  115. else fake("Allocated from chunk.");
  116.  
  117.  
  118.   temp = (u *) s_next_ptr(next_unused); 
  119.  
  120.   *s_size_ptr(next_unused) = size;
  121.   next_unused += size;
  122.   unused_size -= size;
  123.  
  124.   return (char *) temp;
  125. }
  126.  
  127. char *debug_free_ptr;
  128.  
  129. void sfree(ptr)
  130. char *ptr;
  131. {
  132.   u *block;
  133.   u i;
  134.  
  135.   debug_free_ptr = ptr;
  136.   block = (u *) ptr;
  137.   block -= 1;
  138.   if ((*s_size_ptr(block) & MASK) > SMALL_BLOCK_MAX + 1)
  139.     { large_free(ptr); return; }
  140.  
  141.   i = *block - 2;
  142.   count(small_alloc_stat, - (int) ((i+2) << 2));
  143.   count(small_free_stat, (i+2) << 2);
  144.   *s_next_ptr(block) = sfltable[i];
  145.   sfltable[i] = block;
  146.   small_free[i] += 1;
  147. fake("Freed");
  148. }
  149.  
  150. /************************************************/
  151. /*    LARGE BLOCK HANDLER            */
  152. /************************************************/
  153.  
  154. #define BEST_FIT    0
  155. #define FIRST_FIT    1
  156. #define HYBRID        2
  157. int fit_style =BEST_FIT;
  158.  
  159. #define l_size_ptr(p)        (p)
  160. #define l_next_ptr(p)        (*((u **) (p+1)))
  161. #define l_prev_ptr(p)        (*((u **) (p+2)))
  162. #define l_next_block(p)        (p + (*(p)))
  163. #define l_prev_block(p)     (p - (*(p-1)))
  164. #define l_prev_free(p)        (!(*p & PREV_BLOCK))
  165. #define l_next_free(p)        (!(*l_next_block(p) & THIS_BLOCK))
  166.  
  167. void show_block(ptr)
  168. u *ptr;
  169. {
  170.   printf("[%c%d: %d]  ",(*ptr & THIS_BLOCK ? '+' : '-'),
  171.         (int) ptr, *ptr & MASK);
  172. }
  173.  
  174. void show_free_list()
  175. {
  176.    u *p;
  177.    p = free_list;
  178.    while (p) {
  179.      show_block(p);
  180.      p = l_next_ptr(p);
  181.    }
  182.    printf("\n");
  183. }
  184.  
  185. stat large_free_stat;     
  186. void remove_from_free_list(ptr)
  187. u *ptr;
  188. {
  189.    count(large_free_stat, - (int) (*ptr & MASK) << 2);
  190.  
  191.    if (l_prev_ptr(ptr))
  192.      l_next_ptr(l_prev_ptr(ptr)) = l_next_ptr(ptr);
  193.    else
  194.      free_list = l_next_ptr(ptr);
  195.  
  196.    if (l_next_ptr(ptr))
  197.      l_prev_ptr(l_next_ptr(ptr)) = l_prev_ptr(ptr);
  198. }
  199.  
  200. void add_to_free_list(ptr)
  201. u *ptr;
  202. {
  203.   extern int puts();
  204.   count(large_free_stat, (*ptr & MASK) << 2);
  205.  
  206.   if (free_list && l_prev_ptr(free_list)) 
  207.     puts("Free list consistency error.");
  208.  
  209.   l_next_ptr(ptr) = free_list;
  210.   if (free_list) 
  211.     l_prev_ptr(free_list) = ptr;
  212.   l_prev_ptr(ptr) = 0;
  213.   free_list = ptr;
  214. }
  215.  
  216. void build_block(ptr, size)    /* build a properly annotated unalloc block */
  217. u *ptr;
  218. u size;
  219. {
  220.   *(ptr) = (*ptr & PREV_BLOCK) | size;        /* mark this block as free */
  221.   *(ptr+size-1) = size;
  222.   *(ptr+size) &= (MASK | THIS_BLOCK); /* unmark previous block */
  223. }
  224.  
  225. static void mark_block(ptr)        /* mark this block as allocated */
  226. u *ptr;
  227. {
  228.   *l_next_block(ptr) |= PREV_BLOCK;
  229.   *ptr |= THIS_BLOCK;
  230. }
  231.  
  232. /*
  233.  * It is system dependent how sbrk() aligns data, so we simpy use brk()
  234.  * to insure that we have enough.
  235.  */
  236. stat sbrk_stat;
  237. static char *esbrk(size)
  238. u size;
  239. {
  240.   extern char *sbrk();
  241.   extern int brk();
  242.   static char *current_break;
  243.  
  244.   if (current_break == 0)
  245.     current_break = sbrk(0);
  246. #ifdef NLHACK
  247.   /*
  248.    * This is a bad patch.. it just logs whenever a block happens to
  249.    * be too small. If the current block (size, say, 16384) is filled
  250.    * up to 16000, and I need just 512, I get logged as needing 16384..
  251.    * - Zappa
  252.    */
  253.   log_sbrk(size);
  254. #endif
  255.   if (brk(current_break + size) == -1)
  256.     return 0;
  257.   count(sbrk_stat,size);
  258.   current_break += size;
  259.   return current_break - size;
  260. }
  261.  
  262. stat large_alloc_stat;
  263. static char *large_malloc(size, force_more)
  264. u size;
  265. int force_more;
  266. {
  267.   u best_size, real_size;
  268.   u *first, *best, *ptr;
  269.  
  270.   size = (size + 7) >> 2;         /* plus overhead */
  271.   count(large_alloc_stat, size << 2);
  272.   first = best = 0;
  273.   best_size = MASK;
  274.  
  275.   if (force_more)
  276.     ptr = 0;
  277.   else
  278.     ptr = free_list;
  279.  
  280.   while (ptr) {
  281.     u tempsize;
  282.         /* Perfect fit? */
  283.     tempsize = *ptr & MASK;
  284.     if (tempsize == size) {
  285.       best = first = ptr;
  286.       break;        /* always accept perfect fit */
  287.     }
  288.  
  289.         /* does it really even fit at all */
  290.     if (tempsize >= size + SMALL_BLOCK_MAX + 1)
  291.       {
  292.         /* try first fit */
  293.         if (!first) 
  294.       {
  295.         first = ptr;
  296.         if (fit_style == FIRST_FIT)
  297.             break;            /* just use this one! */
  298.       }
  299.         /* try best fit */
  300.     tempsize -= size;
  301.     if (tempsize>0 && tempsize<=best_size) 
  302.       {
  303.         best = ptr;
  304.         best_size = tempsize;
  305.           }
  306.       }
  307.     ptr = l_next_ptr(ptr);
  308.   } /* end while */
  309.  
  310.   if (fit_style==BEST_FIT) ptr = best;
  311.   else ptr = first;    /* FIRST_FIT and HYBRID both leave it in first */
  312.  
  313.   if (!ptr)        /* no match, allocate more memory */
  314.     {
  315.       u chunk_size, block_size;
  316.       block_size = size*SINT;
  317.       if (force_more || (block_size>CHUNK_SIZE))
  318.     chunk_size = block_size;
  319.       else
  320.     chunk_size = CHUNK_SIZE;
  321.  
  322.       if (!start_next_block) {
  323.     start_next_block = (u *) esbrk(SINT);
  324.     if (!start_next_block)
  325.       return 0;
  326.     *(start_next_block) = PREV_BLOCK;
  327. fake("Allocated little fake block");
  328.       }
  329.  
  330.       ptr = (u *) esbrk(chunk_size);
  331.       if (ptr == 0)
  332.       return 0;
  333.       ptr -= 1;        /* overlap old memory block */
  334.       block_size = chunk_size / SINT;
  335.  
  336.                   /* configure header info on chunk */
  337.       
  338.       build_block(ptr,block_size);
  339. if (force_more)
  340. fake("Build little block");
  341. else
  342. fake("Built memory block description.");
  343.       *l_next_block(ptr)=THIS_BLOCK;
  344.       add_to_free_list(ptr);
  345.     }    /* end of creating a new chunk */
  346.   remove_from_free_list(ptr);
  347.   real_size = *ptr & MASK;
  348.  
  349.   if (real_size != size) {
  350.     /* split block pointed to by ptr into two blocks */
  351.     build_block(ptr+size, real_size-size);
  352. fake("Built empty block");
  353.     add_to_free_list(ptr+size);
  354.     build_block(ptr, size);
  355.   }
  356.  
  357.   mark_block(ptr);
  358. fake("built allocated block");
  359.   return (char *) (ptr + 1);
  360. }
  361.  
  362. static void large_free(ptr)
  363. char *ptr;
  364. {
  365.   u size, *p;
  366.   p = (u *) ptr;
  367.   p-=1;
  368.   size = *p & MASK;
  369.   count(large_alloc_stat, - (int) (size << 2));
  370.  
  371.   if (l_next_free(p)) {
  372.     remove_from_free_list(l_next_block(p));
  373.     size += (*l_next_block(p) & MASK);
  374.     *p = (*p & PREV_BLOCK) | size;
  375.   }
  376.  
  377.   if (l_prev_free(p)) {
  378.     remove_from_free_list(l_prev_block(p));
  379.     size += (*l_prev_block(p) & MASK);
  380.     p = l_prev_block(p);
  381.   }
  382.  
  383.   build_block(p, size);
  384.  
  385.   add_to_free_list(p);
  386. }
  387.  
  388. char *srealloc(p, size)
  389. char *p; unsigned size;
  390. {
  391.    unsigned *q, old_size;
  392.    char *t;
  393.    
  394.    q = (unsigned *) p;
  395.    --q;
  396.    old_size = ((*q & MASK)-1)*sizeof(int);
  397.    if (old_size >= size)
  398.       return p;
  399.  
  400.    t = malloc(size);
  401.    if (t == 0) return (char *) 0;
  402.  
  403.    memcpy(t, p, old_size);
  404.    free(p);
  405.    return t;
  406. }
  407.  
  408.  
  409.  
  410. int resort_free_list() { return 0; }
  411. #define dump_stat(str,stat) add_message(str,stat.counter,stat.size)
  412. void dump_malloc_data()
  413. {
  414.   add_message("Type                   Count      Space (bytes)\n");
  415.   dump_stat("sbrk requests:     %8d        %10d (a)\n",sbrk_stat);
  416.   dump_stat("large blocks:      %8d        %10d (b)\n",large_alloc_stat);
  417.   dump_stat("large free blocks: %8d        %10d (c)\n\n",large_free_stat);
  418.   dump_stat("small chunks:      %8d        %10d (d)\n",small_chunk_stat);
  419.   dump_stat("small blocks:      %8d        %10d (e)\n",small_alloc_stat);
  420.   dump_stat("small free blocks: %8d        %10d (f)\n",small_free_stat);
  421.   add_message(
  422. "unused from current chunk          %10d (g)\n\n",unused_size<<2);
  423.   add_message(
  424. "    Small blocks are stored in small chunks, which are allocated as\n");
  425.   add_message(
  426. "large blocks.  Therefore, the total large blocks allocated (b) plus\n");
  427.   add_message(
  428. "the large free blocks (c) should equal total storage from sbrk (a).\n");
  429.   add_message(
  430. "Similarly, (e) + (f) + (g) equals (d).  The total amount of storage\n");
  431.   add_message(
  432. "wasted is (c) + (f) + (g); the amount allocated is (b) - (f) - (g).\n");
  433. }
  434.  
  435. /*
  436.  * calloc() is provided because some stdio packages uses it.
  437.  */
  438. char *calloc(nelem, sizel)
  439. #ifndef MSDOS
  440.     int nelem, sizel;
  441. #else
  442.     unsigned nelem, sizel;
  443. #endif
  444. {
  445.     char *p;
  446.  
  447.     if (nelem == 0 || sizel == 0)
  448.     return 0;
  449.     p = malloc(nelem * sizel);
  450.     if (p == 0)
  451.     return 0;
  452.     (void)memset(p, '\0', nelem * sizel);
  453.     return p;
  454. }
  455.  
  456. /*
  457.  * Functions below can be used to debug malloc.
  458.  */
  459.  
  460. #if 0
  461.  
  462. int debugmalloc;
  463. /*
  464.  * Verify that the free list is correct. The upper limit compared to
  465.  * is very machine dependant.
  466.  */
  467. verify_sfltable() {
  468.     u *p;
  469.     int i, j;
  470.     extern int end;
  471.  
  472.     if (!debugmalloc)
  473.     return;
  474.     if (unused_size > SMALL_CHUNK_SIZE / SINT)
  475.     apa();
  476.     for (i=0; i < SMALL_BLOCK_MAX; i++) {
  477.     for (j=0, p = sfltable[i]; p; p = * (u **) (p + 1), j++) {
  478.         if (p < (u *)&end || p > (u *) 0xfffff)
  479.         apa();
  480.         if (*p - 2 != i)
  481.         apa();
  482.     }
  483.     if (p >= next_unused && p < next_unused + unused_size)
  484.         apa();
  485.     }
  486.     p = free_list;
  487.     while (p) {
  488.     if (p >= next_unused && p < next_unused + unused_size)
  489.         apa();
  490.     p = l_next_ptr(p);
  491.     }
  492. }
  493.  
  494. verify_free(ptr)
  495.     u *ptr;
  496. {
  497.     u *p;
  498.     int i, j;
  499.  
  500.     if (!debugmalloc)
  501.     return;
  502.     for (i=0; i < SMALL_BLOCK_MAX; i++) {
  503.     for (j=0, p = sfltable[i]; p; p = * (u **) (p + 1), j++) {
  504.         if (*p - 2 != i)
  505.         apa();
  506.         if (ptr >= p && ptr < p + *p)
  507.         apa();
  508.         if (p >= ptr && p < ptr + *ptr)
  509.         apa();
  510.         if (p >= next_unused && p < next_unused + unused_size)
  511.         apa();
  512.     }
  513.     }
  514.  
  515.     p = free_list;
  516.     while (p) {
  517.     if (ptr >= p && ptr < p + (*p & MASK))
  518.         apa();
  519.     if (p >= ptr && p < ptr + (*ptr & MASK))
  520.         apa();
  521.     if (p >= next_unused && p < next_unused + unused_size)
  522.         apa();
  523.     p = l_next_ptr(p);
  524.     }
  525.     if (ptr >= next_unused && ptr < next_unused + unused_size)
  526.     apa();
  527. }
  528.  
  529. apa() {
  530.     int i;
  531.     i/0;
  532. }
  533.  
  534. static char *ref;
  535. test_malloc(p)
  536.     char *p;
  537. {
  538.     if (p == ref)
  539.     printf("Found 0x%x\n", p);
  540. }
  541.  
  542. #endif /* 0 (never) */
  543.